package algorithm.排序;

import java.util.Arrays;

/**
 *
 *  算法发明者： Donald Shell
 *
 */
public class ShellSort {


    public static void main(String[] args) {
        int[] arr = {99, 5, 69, 33, 56, 13, 22, 55, 77, 48, 12, 88, 2, 69, 99};
        System.out.println("排序之前数组：");
        printArray(arr);

        //希尔排序
        shellSort(arr);

        System.out.println("希尔排序后数组：");
        System.out.println(Arrays.toString(arr));

    }

    public static void shellSort(int[] arr) {
        int length = arr.length;
        //step折半直到step=1为止,折半过程：15/2=7 --> 7/2=3 -->3/2=1
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                int temp = arr[i];
                int j;
                for (j = i - step; j >= 0 && arr[j] > temp; j -= step) {
                    arr[j + step] = arr[j];
                }
                arr[j + step] = temp;
            }
        }
    }


    /*
     * 最近才知道打印数组不用自己写方法这么麻烦，java API中就有 Arrays.toString(arr);
     * 越简单的越容易忽略，这是最后一次自己写这个方法，以后就用自带的方法
     */
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x != arr.length - 1) {
                System.out.print(arr[x] + ", ");
            } else {
                System.out.println(arr[x] + "]");
            }

        }
    }
}





//  https://www.runoob.com/w3cnote/shell-sort.html

//原理和代码：https://www.jianshu.com/p/d730ae586cf3

//https://www.cnblogs.com/chengxiao/p/6104371.html

